package LC;

import com.sun.xml.internal.ws.api.pipe.ServerTubeAssemblerContext;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC37
 * @Description: TODO
 * @Author hl
 * @Date 2021/4/19
 * @Version V1.0
 **/
public class LC37 {
   static int [][]rows=new int[9][9];
   static int [][]cloumns=new int[9][9];
   static int [][]smallSuDO=new  int[9][9];
   static List<Pair<Integer,Integer>> list=new ArrayList<>();
   static boolean flag=false;
   public static void solveSudoku(char[][] board) {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if (board[i][j]=='.'){
                    list.add(new Pair<>(i,j));
                }else{
                    int num=board[i][j]-'1';
                    rows[i][num]=1;
                    cloumns[j][num]=1;
                    smallSuDO[i/3*3+j/3][num]=1;
                }
            }
        }
        dfs(board,0);
    }

    public static void dfs(char[][] board, int index) {
        if(index==list.size()){
            flag=true;
            return;
        }
        int row=list.get(index).getKey();
        int column=list.get(index).getValue();
        for(int i=0;i<9&&!flag; i++){
            if(rows[row][i]!=1&&cloumns[column][i]!=1&&smallSuDO[row/3*3+column/3][i]!=1){
                rows[row][i]=1;
                cloumns[column][i]=1;
                smallSuDO[row/3*3+column/3][i]=1;
                board[row][column]=(char) (i + '0' + 1);

                dfs(board,index+1);
                rows[row][i]=0;
                cloumns[column][i]=0;
                smallSuDO[row/3*3+column/3][i]=0;
            }
        }
    }
}
